package alogrithm.solution_31_60;

/*
 * 有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
 */
public class P32 {
	public static void makeGapMinimal(int arr1[],int arr2[])
	{
		int sum1=0,sum2=0;
		for(int i:arr1)sum1+=i;
		for(int i:arr2)sum2+=i;
		int gap=sum1-sum2;
		int newGap=gap;
		do
		{
			gap=newGap;
			for(int i=0;i<arr1.length;i++)
			{
				for(int j=0;j<arr2.length;j++)
				{
					int temp=newGap+2*(arr2[j]-arr1[i]);
					if(Math.abs(temp)<Math.abs(newGap))
					{
						int swap=arr1[i];
						arr1[i]=arr2[j];
						arr2[j]=swap;
						newGap=temp;
					}
				}
			}
		}while(Math.abs(newGap)!=Math.abs(gap));
		System.out.println(gap);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr1[]={1, 1, 2, 3, 29};
		int arr2[]={30, 210, 232, 12311, 12312};
		makeGapMinimal(arr1, arr2);
		for(int ele:arr1)
			System.out.print(ele+"\t");
		System.out.println();
		for(int ele:arr2)
			System.out.print(ele+"\t");

	}

}
